#include <iostream>

#define MAX(a,b) a>b?a:b
#define D 10

// #define DEBUG_MOD
#ifdef DEBUG_MOD
#define LOG(i,j) cout << i << "," << j << ":" << __LINE__ << " " << satisfaction[i][j] << endl
#else
#define LOG(i,j)
#endif

using namespace std;

class Item
{
public:
    uint16_t v, vp;    // 价格， 价格*重要度
    
    Item(uint16_t v=0, uint16_t vp=0):
        v(v),vp(vp){}
};

class annexItem : public Item
{
public:
    uint16_t q; // 从属主件编号
    
    annexItem(uint16_t v=0, uint16_t vp=0, uint16_t q=0)
    :Item(v, vp), q(q){}
};

class mainItem : public Item
{
public:
    uint16_t num; // 主件编号
    uint16_t annexCount = 0; // 拥有的附件数
    Item* annexList[2]; // 附件节点地址
    
    mainItem(uint16_t v=0, uint16_t vp=0, uint16_t count = 0):Item(v, vp)
    {
        num = count;
    }
};

class Node
{
public:
    static Node* beginMain;
    static Node* endMain;
    
    static Node* beginAnnex;
    static Node* endAnnex;

    static uint16_t getItemCount;
    
    Item* item = nullptr;
    Node* next = nullptr;
    Node** pAnnex = nullptr;
    
    Node(Item* inItem)
    {
        item = inItem;
    }
    
    static void push_back(Node** endNode, Node* newNode)
    {
        (*endNode)->next = newNode;
        *endNode = (*endNode)->next;
    }

    static void addNode(uint16_t v, uint16_t vp, uint16_t q)
    {
        Node::getItemCount++;
        Node** begin = nullptr;
        Node** end = nullptr;
        Item* item = nullptr;

        if (q == 0){     // 主件
            begin = &Node::beginMain;
            end = &Node::endMain;
            item = new mainItem(v, vp, Node::getItemCount);
        }else{          // 附件
            begin = &Node::beginAnnex;
            end = &Node::endAnnex;
            item = new annexItem(v, vp, q);
        }

        if (*begin == nullptr)
        {
            *begin = new Node(item);
            *end = *begin;
        }
        else
        {
            Node::push_back(end, new Node(item));
        }
    }
};

Node* Node::beginMain = nullptr;
Node* Node::endMain = nullptr;

Node* Node::beginAnnex = nullptr;
Node* Node::endAnnex = nullptr;

uint16_t Node::getItemCount = 0;

int main()
{
    uint16_t N, m;    // 总钱数, 可购买的物品个数
    cin >> N >> m;
    N = N/D;
    
    for (uint16_t v, vp, q; cin >> v >> vp >> q;)
    {
        v = v/D;
        vp = static_cast<uint16_t>(v * vp); // 存着重要程度没用，直接算成价值与重要程度的乘积
        Node::addNode(v, vp, q);
    }

    // 将附件放到主件中
    for (Node* pAnnex = Node::beginAnnex; ; pAnnex = pAnnex->next) // 遍历附件链表
    {
        annexItem* castItemA = static_cast<annexItem*>(pAnnex->item); // 遍历主件链表
        for (Node* pMain = Node::beginMain; ; pMain = pMain->next) // 得到附件对应的主件节点
        {
            mainItem* castItemM = static_cast<mainItem*>(pMain->item);
            
            if (castItemM->num == castItemA->q) // 如果此主件节点编号与附件q相等，则退出遍历
            {
                castItemM->annexList[castItemM->annexCount] = castItemA;
                castItemM->annexCount++;
                break;
            }

            if (pMain == Node::endMain) // 退出遍历主件链表
            {
                cout << "没找到此附件所属的主件" << endl;
                break;
            }
        }

        if (pAnnex == Node::endAnnex) break; // 退出遍历附件链表
    }

    // 主件数量
    uint16_t mainNodeSize = 0;
    for (Node* pMain = Node::beginMain; ; pMain = pMain->next)
    {
        mainNodeSize++;
        if (pMain == Node::endMain) break;
    }

    // 创建用于储存计算结果的二维数组
    uint16_t** satisfaction = new uint16_t*[mainNodeSize+1];
    for (int i = 0; i < mainNodeSize+1; i++)
    {
        satisfaction[i] = new uint16_t[N+1];
    }
    
    // 计算
    Node* pMain = Node::beginMain;
    for (int i = 1; i < mainNodeSize+1; i++)
    {
        mainItem* castItemM = static_cast<mainItem*>(pMain->item);
        for (int j = N; j > 0; j--)
        // for (int j = 1; j < N+1; j++)
        {
            if (j >= castItemM->v) // 剩余金钱要大于等于当前主件的价值
            {
                uint16_t tmpA = satisfaction[i-1][j];
                uint16_t tmpB = satisfaction[i-1][j-castItemM->v] + castItemM->vp;
                satisfaction[i][j] = MAX(tmpA, tmpB);
                LOG(i,j);

                if (castItemM->annexCount != 0) // 拥有附件
                {
                    // 取出第一个附件
                    annexItem* castItemA1 = static_cast<annexItem*>(castItemM->annexList[0]);
                    if (j >= (castItemM->v + castItemA1->v)) // 剩余金钱要大于等于当前主件与附件的价值和
                    {
                        tmpA = satisfaction[i][j];
                        tmpB = satisfaction[i-1][j - castItemM->v - castItemA1->v] 
                                                            + castItemM->vp + castItemA1->vp;
                        satisfaction[i][j] = MAX(tmpA, tmpB);
                        LOG(i,j);
                    }
                    if (castItemM->annexCount == 2) // 拥有两个附件
                    {
                        // 取出第二个附件
                        annexItem* castItemA2 = static_cast<annexItem*>(castItemM->annexList[1]);
                        if (j >= (castItemM->v + castItemA2->v)) // 剩余金钱要大于等于当前主件与附件的价值和
                        {
                            tmpA = satisfaction[i][j];
                            tmpB = satisfaction[i-1][j - castItemM->v - castItemA2->v] 
                                                                + castItemM->vp + castItemA2->vp;
                            satisfaction[i][j] = MAX(tmpA, tmpB);
                            LOG(i,j);

                            if (j >= (castItemM->v + castItemA1->v + castItemA2->v))
                            {
                                tmpA = satisfaction[i][j];
                                tmpB = satisfaction[i-1][j - castItemM->v - castItemA1->v - castItemA2->v] 
                                                                    + castItemM->vp + castItemA1->vp + castItemA2->vp;
                                satisfaction[i][j] = MAX(tmpA, tmpB);
                                LOG(i,j);
                            }
                        }
                    }
                }
            }else{ // 买不起了
                satisfaction[i][j] = satisfaction[i-1][j];
            }
        }
    #ifdef DEBUG_MOD
        cout << endl;
    #endif
        pMain = pMain->next;
    }

    cout << satisfaction[mainNodeSize][N]*D << endl;

    return 0;
}